首先祝各位:APIO & NOI RP++!
题目来源:APIO2020练习赛 B (我不知道大家能不能看到这个链接的题目)
题目翻译
- 这是一道交互题。
- 有一张二分图,左侧有个点,右侧有个点。保证。
- 你可以向交互库提出如下询问:给定一个点集,交互库会返回与中任意点相邻的所有点。
- 你需要通过至多次询问,找到一个度数不为的点。由于,一定存在这样的点。
数据范围:。
一道很考察思维和代码细节的题。(反正我被坑了很久)
首先看数据范围,发现,大概可以猜到需要次查询的算法才能通过。(也可以联想到,不过和此题好像没啥联系)
分析这个交互过程:现在假设你询问了一个同属一侧的点集,返回的结果是。那么:
- 对于任意都存在一个满足相邻。
- 对于任意都不存在一个满足相邻。
乍一看这两句话是废话,就是把询问的方式重新说了一遍。不过我们可以找到一些很好的性质,如果我们现在再查询一下呢?假设返回的集合是。那么:
- 如果有一个点。可以断定的度数一定为,否则如果它和相连,一定有,那么必然,矛盾。
- 如果有一个点。一定存在一个且相连,然后一定存在一个且相连。又因为,。那么同时与相连,度数至少为。
- 换句话说,只要此时,那么我们找到了一个度数不为的点。
如果我们没找到即,那这个二分图中所有的边要么在里,要么在外。这两部分是不连通的,可以递归处理。我们找到这两部分中满足两侧点数不相等且较小的一部分,递归下去。如果我们选取的适当,每次就可以把问题的大小减半,这样就能做到次查询了。
然而这么做的查询次数大概是,并不能过题……考虑优化一下。显然你可以选定一个左点集的子集和右点集的子集,把他们放到一起询问,然后你还能很方便地分开交互库返回的结果。然后发现,之前的分析中的询问和递归后的询问可以合并起来。然后你就糊出了一个复杂度正确但是非常鬼畜的做法。